import bisect
import random

def Mean(t):
	"""Computes the mean of a sequence of numbers.

	Args:
		t: sequence of numbers

	Returns:
		float
	"""
	return float(sum(t)) / len(t);


def MeanVar(t):
	"""Computes the mean and variance of a sequence of numbers.

	Args:
		t: sequence of numbers

	Returns:
		tuple of two floats
	"""
	mu  = Mean(t)
	var = Var(t, mu)
	return mu, var

def Trim(t, p=0.01):
	"""Trims the largest and smallest elements of t.

	Args:
		t: sequence of numbers
		p: fraction of values to trim off each end

	Returns:
		sequence of values
	"""
	n = int(p * len(t))
	t = sorted(t)[n : -n]
	return t

def Jitter(values, jitter=0.5):
	"""Jitters the values by adding a uniform variate in (-jitter, jitter)."""
	return [x + random.uniform(-jitter, jitter) for x in values]

def TrimmedMean(t, p=0.01):
	"""Computes the trimmed mean of a sequence of numbers.

	Side effect: sorts the list

	Args:
		t: sequence of numbers
		p: fraction of values to trim off each end

	Returns:
		float
	"""
	t = Trim(t, p)
	return Mean(t)

def TrimmedMeanVar(t, p=0.01):
	"""Computes the trimmed mean and variance of a sequence of numbers.

	Side effect: sorts the list.

	Args:
		t: sequence of numbers
		p: fraction of values to trim off each end

	Returns:
		float
	"""
	t = Trim(t, p)
	mu, var = MeanVar(t)
	return mu, var

def Var(t, mu=None):
	"""Computes the variance of a sequence of numbers.

	Args:
		t: sequence of numbers
		mu: value around wich to compute the variance: by default,
			computes the mean.

	Return:
		float
	"""
	if mu is None:
		mu = Mean(t)

	dev2 = [(x - mu) **2 for x in t]
	var = Mean(dev2)
	return var

def Binom(n, k, d={}):
	"""Compute the binamial coefficient "n choose k".

	Args:
		n: numbers of trials
		k: numbers of successes
		d: map from (n,k) tuples to cached results

	Returns:
		int
	"""
	if k == 0:
		return 1
	if n == 0:
		return 0

	try:
		return d[n,k]
	except KeyError:
		res = Binom(n-1, k) + Binom(n-1, k-1)
		d[n, k] = res
		return res

class Interpolator(object):
	"""Represents a mapping between sorted sequences; performs linear interp.

	Attributes:
		xs: sorted list
		ys: sorted list
	"""
	def __init__(self, xs, ys):
		self.xs = xs
		self.ys = ys

	def Lookup(self,x):
		"""Looks up x and returns the corresponding value of y."""
		return self._Bisect(x, self.xs, self.ys)

	def Reverse(self, y):
		"""Looks up y and returns the corresponding value of x."""
		return self._Bisect(y, self.ys, seld.xs)

	def _Bisect(self, x, xs, ys):
		"""Helper function."""
		if x <= xs[0]:
			return ys[0]
		if x >= xs[-1]:
			return ys[-1]
		i = bisect.bisect(xs, x)
		frac = 1.0 * (x - xs[i-1]) / (xs[i] - xs[i-1])
		y = ys[i-1] + frac * 1.0 * (ys[i] - ys[i-1])
		return y